package _02_singlyLinkedList;

// 单链表类，T表示数据元素的数据类型；默认继承Object
public class SinglyLinkedList<T> {
    
    // 头指针，指向空单链表的头节点
    public Node<T> head;
    
    // 构造空单链表
    public SinglyLinkedList() {
        // 创建头节点，data和next值均为null
        this.head = new Node<T>();
    }
    
    // 构造单链表，尾插入values数组元素，忽略其中空对象
    public SinglyLinkedList(T[] values) {
        // this(); ==> head.data = null; head.next = null;
        this();
        // 给临时变量rear创建下一个结点，实际上能成功给this.head创建，这是因为在Java中，对象之间的传递是通过引用来实现的。
        // 当我们把this.head赋值给rear时，rear与this.head指向的是同一个对象。
        // 当执行“rear.next = new Node<T>(values[i], null)”这一语句时，我们创建了一个新的节点，并将rear.next设置为指向这个新节点。
        // 由于rear和this.head指向的是同一个对象，当rear.next被设置为指向新节点时，this.head.next同时也被设置为指向新节点。
        Node<T> rear = this.head;
        for (int i = 0; i < values.length; i++) {
            rear.next = new Node<T>(values[i], null);
            rear = rear.next;
        }
    }
    
    // 深拷贝
    public SinglyLinkedList(SinglyLinkedList<T> s) {
        this();
        /*
        // 这样为何不行？因为p一开始赋值为this.head.next，后赋值为new Node(q.data, null);并没有与头结点建立联系
        // 后面又把p的赋值改成p.next把之前创建的新结点覆盖了，那么后面再创建结点再赋值给p.next然后又用p.next.next覆盖掉...
        // 你每个结点都创建了，但是却又只是覆盖掉了，根本没有链接起来...
        Node<T> p = this.head.next;
        for (Node<T> q = s.head.next; q != null; q = q.next) {
            p = new Node<T>(q.data, null);
            System.out.println(p.toString() + ", " + this.head.next.toString());
            p = p.next;
        }*/
        Node<T> p = this.head;
        for (Node<T> q = s.head.next; q != null; q = q.next) {
            p.next = new Node<T>(q.data, null);
            // System.out.println(p.toString() + ", " + this.head.next.toString());
            p = p.next;
        }
    }
    
    // 判空
    public boolean isEmpty() {
        return this.head.next == null;
    }
    
    // 返回第i个元素，0 < i < 单链表长度，若i序号越界，则获取元素
    public T get(int i) {
        Node<T> p = this.head.next;
        
        // 遍历单链表，寻找第i个结点（p指向）
        for (int j = 0; p != null && j < i; j++) {
            p = p.next;
        }
        // 若p指向第i个结点，则返回其元素值
        return (i >= 0 && p != null) ? p.data : null;
    }
    
    // 第i个元素为x，0 <= i < 单链表长度且x != null。
    public void set(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x==null");
        }
        Node<T> p = this.head.next;
        for (int j = 0; j < i; j++) {
            p = p.next;
        }
        if (i >= 0 && p != null) {
            p.data = x;
        } else {
            throw new IndexOutOfBoundsException(i+"");
        }
    }
    
    // 返回单链表的长度
    public int size() {
        Node<T> p = this.head.next;
        int count = 0;
        while (p != null) {
            p = p.next;
            count++;
        }
        return count;
    }
    
    // 返回单链表中所有元素的描述字符串
    public String toString() {
        if (this.isEmpty()) {
            return null;
        }
        String str = "{";
        Node<T> p = this.head.next;
        while (p.next != null) {
            str += p.data.toString() + ", ";
            p = p.next;
        }
        str += p.data.toString();
        return str + "}";
    }
    
    // 插入，插入x为第i个元素，x != null，返回插入节点，对i容错，若i < 0，则头插入，若i > 长度，则尾插入
    // 以头插入为例：head --> head.next; p为插入结点，先让p --> head.next，再让head --> p
    public Node<T> insert(int i, T x) {
        if (x == null) {
            throw new NullPointerException("x==null");
        }
        Node<T> front = this.head;
        for (int j = 0; front.next != null && j < i; j++) {
            front = front.next;
        }
        Node<T> p = new Node<T>(x, front.next);
        front.next = p;
        return p;
    }
    
    // 尾插入
    public Node<T> insert(T x) {
        if (x == null) {
            throw new NullPointerException("x==null");
        }
        Node<T> front = this.head;
        while (front.next != null) {
            front = front.next;
        }
        Node<T> p = new Node<T>(x, front.next);
        front.next = p;
        return p;
    }
    
    // 删除第i个元素，返回被删除的元素
    public T remove(int i) {
        Node<T> front = this.head;
        for (int j = 0; front.next != null && j < i; j++) {
            front = front.next;
        }
        if (i >= 0 && front != null) {
            T x = front.next.data;
            front.next = front.next.next;
            return x;
        }
        return null;
    }
    
    // 顺序查找并返回与key相等的元素；若查找不成功，则返回null
    public Node<T> search(T key) {
        if (key == null) {
            return null;
        }
        for (Node<T> front = this.head.next; front != null; front = front.next) {
            if (key.equals(front.data)) {
                return front;
            }
        }
        return null;
    }

    // 顺序查找并删除首个与key相等的元素，返回被删除元素；若查找不成功，则返回null
    public T remove(T key) {
        if (key != null) {
            for (Node<T> front = this.head; front.next != null; front = front.next) {
                if (front.next.data.equals(key)) {
                    T temp = front.next.data;
                    front.next = front.next.next;
                    return temp;
                }
            }
        }
        return null;
        
    }
    
    // 比较两链表是否相等
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof SinglyLinkedList<?>)) {
            return false;
        }
        SinglyLinkedList<T> s = (SinglyLinkedList<T>)obj;
        if (s.size() != this.size()) {
            return false;
        }
        Node<T> p = s.head.next;
        Node<T> q = this.head.next;
        // 思考：p.data.equals(q.data)这句为什么不可以放前面？
        while (/*p.data.equals(q.data) &&*/ p != null && q != null && p.data.equals(q.data)) {
            p = p.next;
            q = q.next;
        }
        return p == null && q == null;
    }
    
    // 反转单链表算法，头插入法
    // head --> head.next(a0) --> head.next.next(a1) --> head.next.next.next(a2) --> null
    // a0 --> null
    // a1 --> a0 --> null
    // a2 --> a1 --> a0 --> null
    // head --> a2 --> a1 --> a0 --> null
    public static <T> void reverse(SinglyLinkedList<T> s) {
        Node<T> p = s.head.next, front = null;
        while (p != null) {
            // 用succ记住p.next
            Node<T> succ = p.next;
            // 然后将p头插入front
            p.next = front;
            // 然后把front的引用改为p
            front = p;
            // 然后把p的引用改为下一个结点，p = p.next，而p.next已经改变了，所以引用succ
            p = succ;
        }
        // 最后再把头结点插入
        s.head.next = front;
    }
    
    // 集合并，this += list，在this后连接list的所有结点；设置list空
    public void concat(SinglyLinkedList<T> list) {
        Node<T> front = null;
        for (front = this.head; front.next != null; front = front.next);
        front.next = list.head.next;
        list.head.next = null;
    }
    
    // 集合并，this += list，在this后连续深拷贝的list，不改变list
    public void addAll(SinglyLinkedList<T> list) {
        /*
        Node<T> front = null;
        for (front = this.head; front.next != null; front = front.next);
        front.next = list.head.next;
        */
        // 问：为什么一定要深拷贝list？
        SinglyLinkedList<T> sllist = new SinglyLinkedList<T>(list);
        Node<T> front1 = null;
        for (front1 = this.head; front1.next != null; front1 = front1.next);
        front1.next = sllist.head.next;
    }
    
    // 返回并集(this + list)，即返回分别赋值this和list后再连接的单链表，this和list不变
    public SinglyLinkedList<T> union(SinglyLinkedList<T> list) {
        SinglyLinkedList<T> sllist1 = new SinglyLinkedList<T>(this);
        SinglyLinkedList<T> sllist2 = new SinglyLinkedList<T>(list);
        sllist1.addAll(sllist2);
        return sllist1;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Integer[] nums1 = {};
        SinglyLinkedList<Integer> s1 = new SinglyLinkedList<Integer>(nums1);
        Integer[] nums2 = {0};
        SinglyLinkedList<Integer> s2 = new SinglyLinkedList<Integer>(nums2);
        Integer[] nums3 = {0, 1, 2, 3, 4, 5};
        SinglyLinkedList<Integer> s3 = new SinglyLinkedList<Integer>(nums3);
        System.out.println("测试isEmpty()方法：");
        System.out.println(s1.isEmpty() + ", " + s2.isEmpty());
        System.out.println("测试get(int i)方法：");
        System.out.println(s3.get(3));
        System.out.println("测试size()方法：");
        System.out.println(s3.size());
        System.out.println("测试set(int i, T x)和toString()方法：");
        s3.set(2, 100);
        System.out.println(s3.toString());
        System.out.println("测试insert(T key, int i)方法：");
        System.out.println(s3.insert(666, 999) + ", " + s3.toString());
        System.out.println("测试insert(T key)方法：");
        System.out.println(s3.insert(99) + ", " + s3.toString());
        System.out.println("测试remove(int i)方法：");
        System.out.println(s3.remove(6) + ", " + s3.toString());
        System.out.println("测试search(T key)方法：");
        System.out.println(s3.search((Integer)3));
        System.out.println("测试remove(T key)方法：");
        System.out.println(s3.remove((Integer)3) + ", " + s3.toString());
        System.out.println("测试equals(Object obj)方法：");
        SinglyLinkedList<Integer> s4 = new SinglyLinkedList<Integer>(nums3);
        SinglyLinkedList<Integer> s5 = new SinglyLinkedList<Integer>(nums3);
        System.out.println(s4.toString() + s5.toString());
        System.out.println(s4.equals(s5));
        System.out.println("测试深拷贝构造方法：");
        SinglyLinkedList<Integer> s6 = new SinglyLinkedList<Integer>(s5);
        System.out.println(s6.toString());
        System.out.println("测试static void reverse(SinglyLinkedList<T> s6)方法：");
        reverse(s6);
        System.out.println(s6.toString()); 
        System.out.println("测试concat(SinglyLinkedList<T> list)方法：");
        s5.concat(s6);
        System.out.println(s5 + ", " + s6);
        System.out.println("测试addAll(SinglyLinkedList<T> list)方法：");
        s3.addAll(s4);
        System.out.println(s3 + ", " + s4);
        System.out.println("测试union(SinglyLinkedList<T> list)方法：");
        System.out.println(s4.union(s5));
        
        
    }
}
